1611D - Weights Assignment For Tree Edges - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
const int mod = 1e9+7;
 
#define rep(i,j,n) for(long long i=j;i<n;i++)
#define rrep(i,j) for(ll i=j;i>=0;i--)
#define DEB(x) cout<<"##"<<x<<"##"<<endl
#define see(x) cout<<x<<"\n";
#define ll long long
#define pb push_back
#define ft first
#define se second
#define vvi vector<vector<int>>
#define vi vector<int>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#pragma GCC optimize "trapv"// Detects overflow.....(RE)
template <typename Type>
istream &operator>>(istream &in, vector<Type> &vec) {
    int n = vec.size();
    for (int i = 0; i < n; i++)
        in >> vec[i];
    return in;
}
template <typename Type>
ostream &operator<<(ostream &out, vector<Type> &vec) {
    for (auto val : vec)
        out << val << " ";
    return out;
}
void reduceFraction(ll &x, ll &y)
{
    int d;
    d = __gcd(x, y); 
    x = x / d;
    y = y / d;
}
 
string str(int i) {
    return i < 0 ? "" : str((i / 26) - 1) + (char)(97 + i % 26);
}
const int MX = 6e6 + 5; 
 
// ll fact[MX];
// ll ifact[MX];//Inverse of factorial
 
ll bin_power(ll a,ll b,ll mod){
    ll res=1;
    while (b){
        if (b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
// ll ncr(ll n,ll r){
//     if(r>n)
//         return 0;
//     return (fact[n]*ifact[n-r]%mod)*ifact[r]%mod;
// }
/*
    fact[0]=1;
    ifact[0]=1;
    rep(i,1,MX-1){
        fact[i]=(i*fact[i-1])%mod;
        ifact[i]=bin_power(fact[i],mod-2,mod); 
    }
*/
#define int long long
// const int MAX_SIZE = 2800001;
// vector<int>isprime(MAX_SIZE , true);
// vector<int> idx(MAX_SIZE);
// vector<int> prime;
// vector<int>SPF(MAX_SIZE);//SPF[i]=smallest prime factor of number i

// void manipulated_seive(int N) {
//     isprime[0] = isprime[1] = false ;
//     for (int i = 2; i < N ; i++) {
//         if (isprime[i]) {
//             prime.push_back(i);
//             SPF[i] = i;
//         }
//         for (int j = 0; j < (int)prime.size() && i * prime[j] < N && prime[j] <= SPF[i]; j++) {
//             isprime[i * prime[j]] = false;
//             SPF[i * prime[j]] = prime[j] ;
//         }
//     }
//     for (int i = 0; i < (int)prime.size(); i++) {
//         idx[prime[i]] = i + 1;
//     }
// }
// //With sieve
// set<int> primeFactors(int n) {
//     set<int> factors;
//     while (n > 1) {
//         factors.insert(SPF[n]);
//         n /= SPF[n];
//     }
//     if(n>1)factors.insert(n);
//     return factors;
// }
// //Without sieve
// bool isprime_n(ll n){
//   for(ll i=2;i*i<=n;i++){
//     if(n%i==0)return false;
//   }
//   return true;
// }
// vector<int>divisors(1e6,0);

// void precompute_divisors(){
//     for(int i=1;i<=1e6;i++){
//         for(int j=i;j<=1e6;j+=i){
//             divisors[j]++;
//         }
//     }
// }

//  Try to do dry run on large no. of testcases (If not provided make some big tc)
//  to observe the pattern.
//  Edge cases : All elements 0, all -ve .........

// // ********************Think mathematically**************************

// class Pair{
// public:
//     int x,y,d;
//     Pair(int x,int y,int d){
//         this->x=x;
//         this->y=y;
//         this->d=d;
//     }
// };
int d1[8][2]={{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
int d[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
//count dearrangements
ll countDer(int n)
{
    ll der[n + 1] = {0};
    der[1] = 0;
    der[2] = 1;
    for (int i = 3; i <= n; ++i)
        der[i] = (i - 1) * (der[i - 1] +
                            der[i - 2]);
    return der[n];
}
// finding ncr of larger numbers upto 1000 iteratively
ll ncr1(int n , int r){
    if(n<0 || r<0 || r>n) return 0;
    if(r==0)return 1;
    if(r==1)return n;
    ll ans = 1 ; 
    ll k=1;
    for(int i=n ; i>n-r ;i--){
        ans *= i;
        ans/=k;
        k++;
    }
    return ans;
}
long long lcm(long long a,long long b){
    return (a*b)/(__gcd(a,b));
}
set<int> find_factors(int x){
    set<int>ans;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            ans.insert(i);
            if(x/i!=i){
                ans.insert(x/i);
            }
        }
    }
    return ans;
}
vector<int>prime_factor(int n){
    vector<int>ans;
    while(n%2==0){
        n/=2;
        ans.pb(2);
    }
    for(int i=3;i*i<=n;i++){
        while(n%i==0){
            ans.pb(i);
            n/=i;
        }
    }
    if(n>1)ans.pb(n);
    return ans;
}
void solve(){
    int n;
    cin>>n;
    vi par(n),p(n);
    cin>>par>>p;
    vi dist(n+1,-1);
    vi path(n+1,0);
    int root=-1;
    for(int i=0;i<n;i++){
        if(i+1==par[i]){
            root=i+1;
        }
    }
    if(p[0]!=root){
        see(-1);
        return;
    }
    dist[p[0]]=0;
    int mn=-1;
    for(int i=1;i<n;i++){
       if(dist[par[p[i]-1]]==-1){
            see(-1);
            return;
       }
       int x=p[i];
       int val=0;
       val=path[par[p[i]-1]];
       // while(par[x-1]!=x){
       //      x=par[x-1];
       //      val+=dist[x];
       // }
       // dist[p[i]]=max(dist[par[p[i]-1]]+1,mn+1);
       if(val+1>mn){
            dist[p[i]]=dist[par[p[i]-1]]+1;
       }else{
            dist[p[i]]=(mn+1)-val;
       }
       path[p[i]]=dist[p[i]]+val;
       mn=max(mn,dist[p[i]]+val);
    }
    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }
    see("");
}
int32_t main()
{   
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    // manipulated_seive(sqrt(1e9+50));
    while(t--){
        solve();
    }
    return 0;
}